The present invention relates to image processing and more particularly, to the construction of a perceptually optimized color palette for use in displaying an original image of higher color resolution on a device with lower color resolution.
Color images are commonly processed by computers and other digital electronic systems as bitmaps. A bitmap is an array of data representing the color of each picture element or pixel of the image. Since data is required to represent each pixel of an image, the memory necessary to store the image and the time necessary to process the image are determined both by the total number of pixels making up the image and the number of data bits used to describe the color of each pixel, known as the bit depth. The color resolution of a system or subsystem is the total number of colors which can be simultaneously used to reproduce the image. The color resolution is a function of the bit depth. The number of colors that can be simultaneously displayed (C) is given by the function C=2.sup.N, where N is the bit depth. For a system with a bit depth of 24, the color of a pixel can be selected from 16.7 million colors while only 256 colors are available for each pixel in a system with a bit depth of eight bits. Image quality improves with greater bit depth since the perceived "true color" of an image pixel is more likely to be found in a palette of 16.7 million colors than in a palette of 256 colors. On the other hand, three times more memory is required to store an image having 24 bit resolution than eight bit resolution. Likewise, greater bit depth increases the processing requirements and may not be useful with some display technologies, such as LCD devices. The ability to reproduce images at lower color resolutions than the color resolution of the original image is important to reduce system costs, especially for portable LCD-based devices.
Reproducing an image at a lower color resolution requires construction of a palette of colors from which the system can select a color to display as a facsimile of the original pixel color. In other words, in a system with eight bit color only 256 colors will be available to replicate the color of each pixel of an image even though the original color of the pixel may have been selected from a palette of more than 16.7 million colors. A principal objective in constructing a palette is to optimize the selection of colors so that images reproduced at a lower resolution are perceived to contain the same colors or colors that are very close to those of the original image. Several methods of optimizing the selection of colors for a palette have been developed, as described below.
One approach to selecting the colors for a palette is to determine which colors appear most frequently in an image and to fill the palette with the most frequently appearing colors. For example, in an 8 bit system the 256 colors appearing most frequently in the image would be used in the palette. The color of each pixel is mapped to the closest color in the palette when the image is reproduced. This approach may produce a high quality reproduction because any single image is likely to contain relatively few colors and it is likely that the true color of the pixel, or a color very near the pixel's true color, will be in the palette. However, image dependent palettes are usually undesirable when several images are presented simultaneously, as in a windowing environment, or when images are presented in rapid succession because palette switching is visually disruptive and computationally intensive. Braudaway, U.S. Pat. No. 4,907,075, and White et al., U.S. Pat. No. 5,130,701, both describe such systems and are incorporated by reference herein.
Another approach is to construct an image independent palette. One method of constructing an image independent palette is to truncate the high bit color representation of the pixel's color. In this approach the least significant digits of the triplets making up the high bit color representation are discarded until the number of bits remaining corresponds to the system's bit depth. A substantial part of the information provided by the original high bit color description is lost in the truncation process. In addition, the color produced by the display can vary substantially from the pixel's true color.
A complicating factor in choosing optimal colors for a palette for a lower color resolution image reproduction is that more than one system is used to describe color in digital systems. Generally, output devices for digital systems require that a color be defined in terms of the intensities of its red, green, and blue (RGB) components. The RGB color model is a cube in a Cartesian coordinate system with red usually being on the x-axis, blue usually being on the z-axis, and green usually being on the y-axis. Black (minimum intensity of red, green, and blue) is located at the intersection of the red, green, and blue axes and white (maximum intensity of red, green, and blue) is located at the corner diagonally up and across the RGB cube from black. The diagonal between the black and white corners of the RGB color gamut is the gray scale. Any color in the cubic gamut of colors is defined by a point located by the red, green, and blue coordinates. RGB color description is suitable for monitors because the cathode ray tube (CRT) composes each pixel from three subpixels; one having a principally red phosphor, one having a principally green phosphor, and one having a principally a blue phosphor. Alternatively, some monitors include a "white" phosphor together with suitable filters to provide RGB output. In a system with 24 bit color depth the color descriptor is composed of an ordered triplet specifying the intensities of red (8 bits), green (8 bits), and blue (8 bits). The intensity of each of the colors (red, green, and blue) is mapped to a memory which outputs the correct voltage to each of the three electron guns in the CRT causing the three phosphors to output the correct light intensity to achieve the specified color for the pixel. Unfortunately, the RGB mapping is device dependant because the actual color produced depends upon the device. To be optimized for human perception, the color palette must take into account the nonlinear relationship of input and output intensity of the display device which is generally referred to as the gamma function of the device.
A color model utilized in many digital video systems is the YC.sub.B C.sub.R (YUV) color model. The YC.sub.B C.sub.R color space also describes color using an ordered triplet. The ordered triplet specifies three different parameters, namely, luminance (Y), chrominance-blue (C.sub.B), and chrominance-red (C.sub.R). The YC.sub.B C.sub.R color model is also a cube at the intersection of three axes of a Cartesian coordinate system. As with the RGB color model, black (minimum luminance, chrominance-blue, and chrominance-red) in the YC.sub.B C.sub.R color gamut cube is located at the intersection of the axes of the color space. In the YC.sub.B C.sub.R color model white (maximum luminance, minimum chrominance blue and minimum chrominance red) lies on the Y-axis. In recent years, the YC.sub.B C.sub.R color model has become common for image description because research has shown that significant improvement in the compressibility of image data is possible with this color representation. Image compression reduces the memory requirements to store the image and the bandwidth requirements to transmit it. JPEG, MPEG, and H.261/H.263 image and video compression standards all use YC.sub.B C.sub.R color components. Digital television also uses YC.sub.B C.sub.R color components.
YC.sub.B C.sub.R color data can be converted to RGB data, and vice versa, by a matrix transformation. If there is sufficient bit depth a simple mathematical transformation may be satisfactory to transform between YC.sub.B C.sub.R and RGB. However, when a color palette is used the matrix transformation does not produce an optimal palette. When the RGB color gamut is superimposed on the YC.sub.B C.sub.R color gamut, the RGB and YC.sub.B C.sub.R color gamuts only partially overlap. In other words, YC.sub.B C.sub.R color data from a source such as digital video can define colors that are not physically realizable by an RGB device. Including colors from regions of the YC.sub.B C.sub.R color gamut which are not in the RGB color gamut in a palette of RGB colors is a suboptimal use of the limited number of entries available in the color palette.
One technique of selecting a color palette is to subdivide each coordinate axis into segments, then choosing a color point for each color volume. This technique is grossly inefficient for the situation of displaying YC.sub.B C.sub.R images in RGB space, because any regular segmentation for the YC.sub.B C.sub.R axes results in a significant number of color volumes which fall partially or wholly outside the RGB color cube, thus representing colors which are not physically realizable.
Another limitation associated with transforming YC.sub.B C.sub.R color data to RGB color data is that equal incremental differences in the luminance parameter (Y) do not correspond to equal changes in the luminance as perceived by the eye. Friedman et al., U.S. Pat. No. 5,398,120, describe a system for selecting colors for a lower resolution RGB palette. Colors selected for the palette are located at the intersections of three sets of parallel planes projecting perpendicular, respectively, to each the Y, C.sub.B, and C.sub.R axes. The spacing of the planes projecting perpendicular to the Y axis is determined using a cubic function. The cubic function does not include consideration of the contribution of the gamma transfer function of the display to human perception of luminance and therefore does not produce perceptually equal gradations of luminance. Further, no method of selecting appropriate palette colors for other than a 12 bit color resolution is described. In addition, the disclosed technique of ordered dithering does not compensate for error introduced by the necessity to display out-of-gamut colors with palette color choices.
Current NTSC television typically receives signals in the form of Y (luminance), I (in phase), and Q (out of phase). The luminance component (Y) is a mixture of red, green, and blue and tends to be most sensitive to green. The in-phase (I) component is generally considered the red component. The out of phase (Q) component is generally considered the blue component. The typical ratios of the Y, I, and Q are [4, 1, 1/4] to approximate the optical characteristics of the human visual system. Accordingly, less of the blue component (Q) is transmitted than the red component (I) which, in turn, is generally less than the green component (Y). To further reduce the bandwidth requirements normally the Q component is amplitude limited.
What is desired, therefore, is a method for constructing a color palette which produces a perceptually optimal distribution of colors for use in reproducing original images having a higher color resolution and represented by color data in the YC.sub.B C.sub.R color space on a device of lower resolution requiring color data in the RGB color space.